package leetcode.tree;

/**
 * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 * <p>
 * 有效 二叉搜索树定义如下：
 * <p>
 * 节点的左子树只包含 小于 当前节点的数。
 * 节点的右子树只包含 大于 当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 */
public class LeetCode98_IsValidBST {

    long pre = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        return inOrder(root);
    }

    public boolean inOrder(TreeNode root) {
        if (root == null) {
            return true;
        }
        boolean l = inOrder(root.left);
        if (root.val <= pre) {
            return false;
        }
        pre = root.val;
        boolean r = inOrder(root.right);
        return l && r;
    }

    public boolean judge(TreeNode root, Integer lower, Integer upper) {
        if (root == null) {
            return true;
        }

        if (lower != null && root.val < lower) return false;
        if (upper != null && root.val > upper) return false;

        return judge(root.left, lower, root.val) && judge(root.right, root.val, upper);
    }
}
